<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
        1 递归法：
          时间复杂度O(n)
          空间O(n)
        */
        function isSubtree(s, t) {
            if (!s) return false; 
            let queue = []; 
            queue.push(s); 

            while (queue.length) {
                let node = queue.shift(); 

                if (isSameTree(node, t)) {
                    return true; 
                }

                if (node.left) queue.push(node.left);
                if (node.right) queue.push(node.right);
            }
            return false;
        }

        // 这个函数里面还是用到了递归
        function isSameTree(s, t) {
            if (!s && !t) return true; 
            if (!s || !t) return false;
            if (s.val !== t.val) return false;

            return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
        }

        function Node(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var a = new Node(1)
        var b = new Node(2)
        var c = new Node(3)
        var d = new Node(2)
        var e = new Node(1)
        var f = new Node(2)
        var g = new Node(3)
        // var g = new Node(3)
        a.left = b
        a.right = c
        d.left = e
        e.left = f
        e.right = g
        console.log(a);
        console.log(d);
        console.log(isSubtree(d, e));
    </script>
</body>

</html>